package basic.courseLearn02.problem;

import org.junit.Test;
import basic.utils.CommonUtil;

public class NetherlandsFlag {

    //荷兰国旗问题，小数放左侧，等于数放中间，大数放右侧
    public int[] netherlandsFlag(int[] arr,int flag){
        int leftIndex=0,rightIndex=arr.length-1;
        for (int i = 0; i <=rightIndex; i++) {
            if (arr[i]<flag){       //小数
                if (i>leftIndex){
                    CommonUtil.swap(arr,leftIndex,i);
                }
                leftIndex++;
            }else if(arr[i]>flag) {   //大数
                CommonUtil.swap(arr,i,rightIndex);
                rightIndex--;
                i--;
            }
        }
        return arr;
    }

    @Test
    public void test(){
//        int[] arr = new int[]{-57,14,-46,1,-9,-62,-16,-29,3,32 };
//        System.out.println(CommonUtil.printArray(netherlandsFlag(arr,21)));
//        System.out.println(check(arr,21));
        executeCheckAlgorithm(1_0000,1000,1000);
    }

    //核实操作
    public boolean check(int[] arr,int flag){
        int a=-1,b=-1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]==flag){
                a=i;break;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>flag){
                b=i;
                break;
            }
        }
        //前部分都是比flag小
        for (int i = 0; i < a; i++) {
            if (arr[i]>=flag)   return false;
        }
        //中部分都是等于flag
        for (int i = a; i < b && a!=-1 && b!=-1; i++) {
            if (arr[i]!=flag)   return false;
        }
        //后部分都是比flag大
        for (int i = b; i < arr.length && b!=-1; i++) {
            if (arr[i]<=flag)   return false;
        }
        return true;

    }

    //对数器操作
    public void executeCheckAlgorithm(int loopNum, int size, int limit){
        boolean right =true;
        int[] arr;
        for (int i = 0; i < loopNum; i++) {
//        1.生成数组result_a
            arr= CommonUtil.generateArrays(size,limit);

//        2.生成数组
            int temp1 = (int)(Math.random()*(limit+1));
            int temp2 = (int)(Math.random()*(limit+1));
            int flag = temp1-temp2;
            int[] tempArray= netherlandsFlag(arr,flag);


//        4.核实比对两数组
            if (!check(tempArray,flag)){
                System.out.println("oh my god");
                System.out.println(CommonUtil.printArray(tempArray));
                System.out.println(flag);
                right=false;
                break;
            }
        }
        if (right){
            System.out.println("very good");
        }
    }


}
